package com.dyz.leetcode._20_dynamicProgramming.knapsack;

public class knapsack03 {
    //动态规划 i表示第几个物品， w表示物品重量
    //dp[i][j] = dp[i-1][c]  c<w[i]
    //dp[i][j] = MaX(dp[i-1][c], dp[i-1][c-w[i]]+v[i])  c>=w[i]
    public int knapsack(int[] w, int[] v, int C) {
        // 1. 状态定义：dp[i][c] 表示从 [0...i] 中选取物品放入容量为 c 的背包中的最大价值
        int[][] dp = new int[w.length][C + 1];

        // 2. 状态初始化
        // 考虑将第 0 号物品放入背包中
        for (int c = 0; c <= C; c++) {
            dp[0][c] = (c >= w[0] ? v[0] : 0);
        }

        // 3. 状态转移
        for (int i = 1; i < w.length; i++) {
            for (int c = 0; c <= C; c++) {
                if (c < w[i]) {
                    dp[i][c] = dp[i - 1][c];
                } else {
                    dp[i][c] = Math.max(dp[i - 1][c], v[i] + dp[i - 1][c - w[i]]);
                }
            }
        }

        return dp[w.length - 1][C];
    }

}
